package 链表;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/linked-list-random-node/
 */
public class _382_链表随机节点 {

    public static void main(String[] args) {
        System.out.println(Math.random());
    }

    /**
     * 暴力解法  通过数组 然后随机数抽取
     */
    /*private List<Integer> target;
    private Random random;
    public _382_链表随机节点(ListNode head) {
        target = new ArrayList<>();
        while (head != null) {
            target.add(head.val);
            head = head.next;
        }
        random = new Random();
    }

    public int getRandom() {
        return target.get(random.nextInt(target.size()));
    }*/

    /**
     * 水塘抽样算法
     */
    private ListNode head;
    private Random random;
    public _382_链表随机节点(ListNode head) {
        this.head = head;
        random = new Random();
    }

    public int getRandom() {
        int i = 1, ans = 0;
        for (ListNode node = head; node != null; node = node.next) {
            if (random.nextInt(i) == 0) {
                ans = node.val;
            }
            ++i;
        }
        return ans;
    }
}

